import java.util.*;
public class SortColor  {
     private static int partition(int[] arr, int l, int r){

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
       // swap( arr, l , (int)(Math.random()*(r-l+1))+l );

        int v = arr[l];

        int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i] > v ){
                j ++;
                swap(arr, j, i);
            }

        swap(arr, l, j);

        return j;
      }
    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    private static int solve(int[] nums, int l, int r, int k){
    	k=k-1;

        if( l == r )
            return nums[l];

        // partition之后, nums[p]的正确位置就在索引p上
        int p = partition(nums, l, r);

        if( k == p )    // 如果 k == p, 直接返回nums[p]
            return nums[p];
        else if( k < p )    // 如果 k < p, 只需要在nums[l...p-1]中找第k小元素即可
            return solve( nums, l, p-1, k);
        else // 如果 k > p, 则需要在nums[p+1...r]中找第k-p-1小元素
             // 注意: 由于我们传入__selection的依然是nums, 而不是nums[p+1...r],
             //       所以传入的最后一个参数依然是k, 而不是k-p-1
            return solve( nums, p+1, r, k );
    }
//    public int findKthLargest(int[] nums, int k) {
//       //assert nums != null && k >= 0 && k < nums.length;
//        
//       return solve(nums, 0, nums.length - 1, k);
//        
//    }
    public static void main(String[] args) {
		int[] nums = {-1,2,0};
		int k = 3;
		System.out.println(solve(nums, 0, nums.length - 1, k));
	}
}

